Many computer vision problems involve assigning a label to each pixel within an image. These labels may, for example, indicate whether the pixel is part of the background or foreground (e.g. for image segmentation). Depending on the application, the label may be selected from two possible labels (a binary label situation) or from a larger number of labels (a multi-label situation). In some applications the number of labels can be very large (tens or hundreds of labels).
A number of techniques have been developed and applied to computer vision problems, such as graph cut, tree-reweighted message passing (TRW), belief propagation (BP), iterated conditional modes (ICM) and simulated annealing (SA). Many of these techniques are applicable to both binary label problems and a multi-label problems, for example, graph cut may be extended by α-expansion. However, α-expansion does not scale well for large numbers of labels because it visits labels exhaustively and therefore the time taken is proportional to the number of possible labels. This linear dependency is also true for many other methods.